#include <stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,a[101][101],b[101][101],i,j,maxn=0;
        scanf("%d",&n);
        for (i=0;i<n;i++)
            for (j=0;j<=i;j++)
                {scanf("%d",&a[i][j]);b[i][j]=0;}
        b[0][0]=a[0][0];
        for (i=1;i<n;i++)
            for (j=0;j<=i;j++)
            {
                if (j==0)b[i][j]=b[i-1][j]+a[i][j];
                else if (j==i)b[i][j]=b[i-1][j-1]+a[i][j];
                else 
                {
                    if (b[i-1][j-1]>b[i-1][j])b[i][j]=b[i-1][j-1]+a[i][j];
                    else b[i][j]=b[i-1][j]+a[i][j];
                }
            }
        for (i=0;i<n;i++)
            if (maxn<b[n-1][i])maxn=b[n-1][i];
        printf("%d\n",maxn);
    }
    return 0;
}
